Routing devices within a network, often referred to as routers, maintain routing information that describe available routes through the network. Upon receiving an incoming packet, the router examines information within the packet and forwards the packet in accordance with the routing information. In order to maintain an accurate representation of the network, routers exchange routing information in accordance with one or more defined routing protocol, such as a link state protocol Interior Gateway Protocol (IGP).
The connection between two devices on a network is generally referred to as a link. A link state protocol, as one type of IGP, allows routers to exchange and accumulate information describing the various links within the network. With a typical link state routing protocol, the routers exchange information related to available interfaces, metrics and other variables associated with network links. This allows a router to construct its own topology or map of the network. Some examples of link state protocols include the Open Shortest Path First (OSPF) protocol and the Intermediate-System to Intermediate System (IS-IS) protocol.
Upon failure of a link or failure of a node interfacing with the link, routers in the network transmit new connectivity information to neighboring devices, allowing each device to update its local routing table. When a link or node in the network fails, routers using traditional link state protocols may take a long time to adapt their forwarding tables in response to the topological change resulting from link and node failures in the network. The process of adapting the forwarding tables is known as convergence. This time delay occurs because recovery from a failure requires each router to re-compute the shortest path algorithm to calculate the next hop for the affected routers in the network. Until the next hops are re-computed, traffic being sent toward the failed link or node may be dropped.
One approach to reduce failure recovery time is to select an alternate next-hop in addition to the best next-hop for a destination. Along with the best next-hop, the alternate next-hop is installed in the packet forwarding engine. When a link or node failure occurs, the router uses the alternate next-hop for packet forwarding until the shortest path algorithm has re-computed the next hops for the updated network topology and installed the re-computed next hops in the packet forwarding engine.